package arithmetic.demo2;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 *
 * 题目： 深搜_优美的排列
 *
 */
class Solution {
    private boolean[] check;
    int ret ; 
    public int countArrangement(int n) {
        // new 上一个空间
        check = new boolean[n+1];
        ret = 0;

        
        dfs(1,n);

        return ret;
    }

   private void  dfs(int pos, int n) {
        // 递归出口
        if(pos == n+1) {
            ret++;
            return;
        }

        for(int i = 1; i <= n; i++) {
            if(!check[i] &&  (i % pos == 0 || pos % i == 0)) {
                check[i] = true;
               dfs(pos+1, n); 
               
                    //    恢复现场
                    check[i] = false; 
            }

        }
   }
}


class Solution1 {
    private boolean[] col ;
    private boolean[]  dig1;
    private boolean[]  dig2;

    List<List<String>> ret ;
    public List<List<String>> solveNQueens(int n) {
        // 实例化对象
        StringBuilder path = new StringBuilder();
        col = new boolean[n];
        // 主对角线
        dig1 = new boolean[20];
        // 反对角线
        dig2 = new boolean[20];

        ret = new ArrayList<>();

        dfs(path,0, n);

        return ret;
    }

    private void dfs( StringBuilder path, int pos, int len ) {


        // 递归出口
        if(pos == len) {
            List<String> list = new ArrayList<>();
            list.add(path.toString());
            ret.add(list);
            return;
        }

        // 开始遍历
        for(int i =0; i < len; i++) {
            if(!col[i] && !dig1[ pos - i + len] && !dig2[pos + i]) {

                path.append("Q");
                col[i] = true;
                dig1[pos - i + len] = true;
                dig2[pos - i] = true;
                dfs(path, pos + 1, len);
            } else {
                path.append(".");
            }
        }
    }
}


/**
 * 题目: 深搜_N皇后
 */

class Solution2 {

    private boolean[] col;
    private boolean[] dig1;
    private boolean[] dig2;

    private List<List<String>> ret;
    private int len;

    private char[][] path ;

    public List<List<String>> solveNQueens(int n) {
        // 实例化对象
        path = new char[n][n];
        col = new boolean[n];
        // 主对角线
        dig1 = new boolean[20];
        // 辅对角线
        dig2 = new boolean[20];

        len = n;

        ret = new ArrayList<>();

        // 全部填充为 .
        for(int i =0; i < len; i++) {
            Arrays.fill(path[i],'.');

        }

        // 开始递归
        dfs(0);

        return ret;
    }

    private void dfs(int row) {
        // 递归出口
        if (row == len) {
            List<String> list = new ArrayList<>();
            for(int i = 0; i < len; i++) {
                list.add(new String(path[i]));
            }
            ret.add(list);
            return;
        }

        // 开始遍历
        for (int i = 0; i < len; i++) {
            if (!col[i] && !dig1[row - i + len] && !dig2[row + i]) {

                // 该位置可以放, 就修改为 'Q'.
                path[row][i]='Q';
                col[i] = true;
                dig1[row - i + len] = true;
                dig2[row + i] = true;

                // 向下深搜
                dfs(row + 1);

                // 恢复现场
                col[i] = false;
                dig1[row - i + len] = false;
                dig2[row + i] = false;
                path[row][i] = '.';
            }
        }
    }
}


/**
 * 题目： 深搜_有效的数独
 *
 */

class Solution3 {
    List<List<Character>> checkRow;
    List<List<Character>> checkCol;
    List<List<Character>> checkRound;

    public boolean isValidSudoku(char[][] board) {

        // 实例化对象
        checkRow = new ArrayList<>();
        checkCol = new ArrayList<>();
        checkRound = new ArrayList<>();
        for (int i = 0; i < 9; i++) {
            List<Character> list1 = new ArrayList<>();
            checkRow.add(list1);
            List<Character> list2 = new ArrayList<>();
            checkCol.add(list2);
            List<Character> list3 = new ArrayList<>();
            checkRound.add(list3);
        }

        // 分情况放入
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] >= '0' && board[i][j] <= '9') {
                    if (!checkRow.get(i).contains(board[i][j])) {
                        hashRow(board, i, j);
                    } else {
                        return false;
                    }

                    if(!checkCol.get(j).contains(board[i][j])) {
                        hashCol(board,i,j);
                    } else {
                        return false ;
                    }

                    if(!checkRound.get(findRound(i, j)).contains(board[i][j])) {
                        hahsRound(board, i, j);
                    }   else {
                        return false;
                    }

                }
            }
        }

        return true;

    }

    private void hashRow(char[][] board, int row, int col) {
        switch (row) {
            case 1:
                checkRow.get(row).add(board[row][col]);
            case 2:
                checkRow.get(row).add(board[row][col]);
            case 3:
                checkRow.get(row).add(board[row][col]);
            case 4:
                checkRow.get(row).add(board[row][col]);
            case 5:
                checkRow.get(row).add(board[row][col]);
            case 6:
                checkRow.get(row).add(board[row][col]);
            case 7:
                checkRow.get(row).add(board[row][col]);
            case 8:
                checkRow.get(row).add(board[row][col]);
            case 0:
                checkRow.get(row).add(board[row][col]);

        }
    }

    private void hashCol(char[][] board, int row, int col) {
        switch (row) {
            case 1:
                checkCol.get(col).add(board[row][col]);
            case 2:
                checkCol.get(col).add(board[row][col]);
            case 3:
                checkCol.get(col).add(board[row][col]);
            case 4:
                checkCol.get(col).add(board[row][col]);
            case 5:
                checkCol.get(col).add(board[row][col]);
            case 6:
                checkCol.get(col).add(board[row][col]);
            case 7:
                checkCol.get(col).add(board[row][col]);
            case 8:
                checkCol.get(col).add(board[row][col]);
            case 0:
                checkCol.get(col).add(board[row][col]);

        }
    }

    private int findRound(int row, int col) {
        if (row >= 0 && row <= 2 && col >= 0 && col <= 2) {
            return 0;
        } else if (row >= 0 && row <= 2 && col >= 3 && col <= 5) {
            return 1;
        } else if (row >= 0 && row <= 2 && col >= 6 && col <= 8) {
            return 2;

        } else if (row >= 3 && row <= 5 && col >= 0 && col <= 2) {
            return 3;

        } else if (row >= 3 && row <= 5 && col >= 3 && col <= 5) {
            return 4;

        } else if (row >= 3 && row <= 5 && col >= 6 && col <= 8) {
            return 5;

        } else if (row >= 6 && row <= 8 && col >= 0 && col <= 2) {
            return 6;

        } else if (row >= 6 && row <= 8 && col >= 3 && col <= 5) {
            return 7;

        } else if (row >= 6 && row <= 8 && col >= 6 && col <= 8) {
            return 8;

        }

        return -1;
    }

    private void hahsRound(char[][] board, int row, int col) {
        int pos = findRound(row, col);
        switch (pos) {
            case 1:
                checkRound.get(pos).add(board[row][col]);
            case 2:
                checkRound.get(pos).add(board[row][col]);
            case 3:
                checkRound.get(pos).add(board[row][col]);
            case 4:
                checkRound.get(pos).add(board[row][col]);
            case 5:
                checkRound.get(pos).add(board[row][col]);
            case 6:
                checkRound.get(pos).add(board[row][col]);
            case 7:
                checkRound.get(pos).add(board[row][col]);
            case 8:
                checkRound.get(pos).add(board[row][col]);
            case 0:
                checkRound.get(pos).add(board[row][col]);

        }
    }
}


/**
 *
 * 方法二：
 * 利用哈希映射数组来解决问题
 */

class Solution4 {

    private boolean Row[][];
    private boolean Col[][];
    private boolean Grid[][][];

    public boolean isValidSudoku(char[][] board) {
        // 实例化空间
        Row = new boolean[9][10];
        Col = new boolean[9][10];
        Grid = new boolean[3][3][10];

        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {

                if (board[i][j] >= '0' && board[i][j] <= '9') {
                    int num = board[i][j] - '0';
                    if (Row[i][num]) {
                        return false;
                    } else {
                        Row[i][num] = true;
                    }

                    if (Col[j][num]) {
                        return false;
                    } else {
                        Col[j][num] = true;
                    }

                    if (Grid[i / 3][j / 3][num]) {
                        return false;
                    } else {
                        Grid[i / 3][j / 3][num] = true;
                    }
                }

            }
        }

        return true;
    }
}

